//
//	File: OyDataStruct.h
//

#ifndef OYDATASTRUCT_H
#define OYDATASTRUCT_H

#ifndef NULL
#define NULL 0
#endif


#define	_MIN( a, b ) (( a < b ) ? (a) : (b))       


/**************************************************************************************
      OOOOO               AA                                    
     OO   OO              AA                                    
    OO     OO            AAAA                                   
    OO     OO  yy  yy    AAAA   rrrrr rrrrr  aaaaa   yy  yy     
    OO     OO  yy  yy   AA  AA  rrr   rrr   aa   aa  yy  yy     
    OO     OO  yy  yy   AA  AA  rr    rr         aa  yy  yy     
    OO     OO  yy  yy   AAAAAA  rr    rr     aaaaaa  yy  yy     
    OO     OO   yyyy   AA    AA rr    rr    aa   aa   yyyy      
     OO   OO    yyyy   AA    AA rr    rr    aa  aaa   yyyy      
      OOOOO      yy    AA    AA rr    rr     aaaaaa    yy       
                 yy                                    yy       
               yyy                                   yyy        
***************************************************************************************/
template< class DataType >
class OyArray
{
public:
	DataType* m_array;
	unsigned int m_size;

public:
	OyArray() { m_array = NULL; m_size = 0; }

	OyArray(unsigned int nSize)
	{
		m_array = (DataType*)calloc( nSize, sizeof(DataType) );
		m_size = nSize;
	}

	~OyArray()
	{
		if( m_array )
			free( m_array );
		m_array = NULL;
	}

	void Init( unsigned int nSize )
	{
		m_array = (DataType*)calloc( nSize, sizeof(DataType) );
		m_size = nSize;
	}

	// Resize the array to a new size. If return false is Out of memory
	bool Resize( unsigned int nNewSize )
	{
		DataType *OldBuffer = m_array;

		if( (m_array = (DataType*)realloc( m_array, nNewSize * sizeof(DataType) )) == NULL )
		{
			free(OldBuffer);
			OldBuffer = NULL;
			m_size = 0;
			return false;
		}

		m_size = nNewSize;
		return true;
	}

	// Inserts a cell in between two others.
	void Insert( DataType item, int index )
	{
		// move everything after index up by one cell.
		for(int i = m_size - 1; i > index; i--)
		{
			m_array[index] = m_array[index - 1];
		}
		// insert the item.
		m_array[index] = item;
	}

	// Removes a cell
	void Remove( int index )
	{
		// move everything after index down by one cell.
		for( int i = index + 1; i < m_size; i++ )
			m_array[i - 1] = m_array[i];
	}

	DataType& operator[] ( int index ) { return m_array[index]; }
	operator DataType* () { return m_array; }
	int Size() { return m_size; }
};


/**************************************************************************************
    DDDDDD                      bb       ll           LL      ii           kk                   dd  LL      ii                  
    DD   DD                     bb       ll           LL      ii           kk                   dd  LL      ii           tt     
    DD    DD                    bb       ll           LL                   kk                   dd  LL                   tt     
    DD    DD   ooooo   uu   uu  bbbbbb   ll   eeeee   LL      ii  nnnnnn   kk  kk  eeeee    dddddd  LL      ii   sssss  tttt    
    DD    DD  oo   oo  uu   uu  bbb  bb  ll  ee   ee  LL      ii  nn   nn  kk kk  ee   ee  dd  ddd  LL      ii  ss   ss  tt     
    DD    DD  oo   oo  uu   uu  bb   bb  ll  ee   ee  LL      ii  nn   nn  kkkk   ee   ee  dd   dd  LL      ii  ss       tt     
    DD    DD  oo   oo  uu   uu  bb   bb  ll  eeeeeee  LL      ii  nn   nn  kkk    eeeeeee  dd   dd  LL      ii   sssss   tt     
    DD    DD  oo   oo  uu   uu  bb   bb  ll  ee       LL      ii  nn   nn  kkkk   ee       dd   dd  LL      ii       ss  tt     
    DD   DD   oo   oo  uu  uuu  bbb  bb  ll  ee   ee  LL      ii  nn   nn  kk kk  ee   ee  dd  ddd  LL      ii  ss   ss  tt     
    DDDDDD     ooooo    uuuuuu  bbbbbb   ll   eeeee   LLLLLLL ii  nn   nn  kk  kk  eeeee    dddddd  LLLLLLL ii   sssss    tt    
***************************************************************************************/                                                                                                                                
// forward declarations of all the classes in this file
template<class DataType> class DoubleListNode;
template<class DataType> class DoubleLinkedList;
template<class DataType> class DoubleListIterator;

// This is the Doubly-linked list node class.
template<class DataType>
class DoubleListNode
{
public:
	DataType m_data;
	DoubleListNode<DataType>* m_next;
	DoubleListNode<DataType>* m_previous;

public:
	void DelLink()
    {
        // if a previous node exists, then make the previous
        // node point to the next node.
        if( m_previous != 0 )
            m_previous->m_next = m_next;

        // if the next node exists, then make the next node
        // point to the previous node.
        if( m_next != 0 )
            m_next->m_previous = m_previous;
    }

	// Insert a node after the current node
    void InsertAfter( DataType p_data )
    {
        // create the new node.
        DoubleListNode<DataType>* newnode = new DoubleListNode<DataType>;
        newnode->m_data = p_data;

        // set up newnode's pointers.
        newnode->m_next     = m_next;
        newnode->m_previous = this;

        // if there is a node after this one, make it point to
        // newnode
        if( m_next != 0 )
            m_next->m_previous = newnode;

        // make the current node point to newnode.
        m_next = newnode;
    }

	// Insert a node before the current node
	void InsertBefore( DataType p_data )
    {
        // create the new node.
        DoubleListNode<DataType>* newnode = new DoubleListNode<DataType>;
        newnode->m_data = p_data;

        // set up newnode's pointers.
        newnode->m_next     = this;
        newnode->m_previous = m_previous;

        // if there is a node before this one, make it point to
        // newnode
        if( m_previous != 0 )
            m_previous->m_next = newnode;

        // make the current node point to newnode.
        m_previous = newnode;
    }
};

// This is the Doubly-linked list container
template<class DataType>
class DoubleLinkedList
{
public:
	DoubleListNode<DataType>* m_head;
	DoubleListNode<DataType>* m_tail;
	int m_count;

public:
	DoubleLinkedList()
	{
		m_head = 0;
        m_tail = 0;
        m_count = 0;
	}

    ~DoubleLinkedList()
    {
        DoubleListNode<DataType>* node = m_head;
        DoubleListNode<DataType>* next;

        while( node != 0 )
        {
            next = node->m_next;
            delete node;
            node = next;
        }
    }

	int Size()
    {
        return m_count;
    }

	// Adds a new node to the end of a list
	void Append( DataType p_data )
    {
        // if there is no head node (ie: list is empty)
        if( m_head == 0 )
        {
            // create a new head node.
            m_head = m_tail = new DoubleListNode<DataType>;
            m_head->m_data = p_data;
            m_head->m_next = 0;
            m_head->m_previous = 0;
        }
        else
        {
            // insert a new node after the tail, and reset the tail.
            m_tail->InsertAfter( p_data );
            m_tail = m_tail->m_next;
        }
        m_count++;
    }

	// Addss a new node to the beginning of a list
	void Prepend( DataType p_data )
    {
        // if there is no head node (ie: list is empty)
        if( m_head == 0 )
        {
            // create a new head node.
            m_head = m_tail = new DoubleListNode<DataType>;
            m_head->m_data = p_data;
            m_head->m_next = 0;
            m_head->m_previous = 0;
        }
        else
        {
            // insert a new node before the head, and reset the head.
            m_head->InsertBefore( p_data );
            m_head = m_head->m_previous;
        }
        m_count++;
    }

	// removes the very first node in the list
	void RemoveHead()
    {
        DoubleListNode<DataType>* node = 0;

        if( m_head != 0 )
        {
            node = m_head->m_next;

            // then delete the head, and make the pointer point to node.
            delete m_head;
            m_head = node;

            // if the head is null, then we've just deleted the only node
            // in the list. set the tail to 0.
            // if not, set the previous pointer to 0.
            if( m_head == 0 )
                m_tail = 0;
            else
                m_head->m_previous = 0;

            m_count--;
        }
    }

	// removes the very last node in the list
	void RemoveTail()
    {
        DoubleListNode<DataType>* node = 0;

        if( m_tail != 0 )
        {
            node = m_tail->m_previous;

            // then delete the head, and make the pointer point to node.
            delete m_tail;
            m_tail = node;

            // if the tail is null, then we've just deleted the only node
            // in the list. set the head to 0.
            // if not, set the next pointer to 0.
            if( m_tail == 0 )
                m_head = 0;
            else
                m_tail->m_next = 0;

            m_count--;
        }
    }

	// Inserts data after the iterator, or at the end of the list if iterator is invalid
	void InsertAfter( DoubleListIterator<DataType>& p_iterator, DataType p_data )
    {
        if( p_iterator.m_node != 0 )
        {
            // insert the data after the iterator
            p_iterator.m_node->InsertAfter( p_data );

            // if the iterator was the tail of the list, reset the tail pointer
            if( p_iterator.m_node == m_tail )
                m_tail = m_tail->m_next;

            m_count++;
        }
        else
        {
            Append( p_data );
        }
    }

	// inserts data before the iterator, or prepends it to the beginning of the list if invalid.
	void InsertBefore( DoubleListIterator<DataType>& p_iterator, DataType p_data )
    {
        if( p_iterator.m_node != 0 )
        {
            // insert the data before the iterator
            p_iterator.m_node->InsertBefore( p_data );

            // if the iterator was the head of the list, reset the head pointer.
            if( p_iterator.m_node == m_head )
                m_head = m_head->m_previous;

            // increment the count
            m_count++;
        }
        else
        {
            Prepend( p_data );
        }
    }

	// Removes the node that the iterator points to and moves iterator forward to the next node.
	void Remove( DoubleListIterator<DataType>& p_iterator )
    {
        DoubleListNode<DataType>* node;
        if( p_iterator.m_node == 0 )
            return;

        // save the pointer to the node we want to delete.
        node = p_iterator.m_node;

        // if the node we want to remove is the head or the tail
        // nodes, then move the head or tail to the next or previous node.
        if( node == m_head )
        {
            m_head = m_head->m_next;
        }
        else if( node == m_tail )
        {
            m_tail = m_tail->m_previous;
        }

        // move the iterator forward to the next valid node
        p_iterator.Forth();

        // delink and delete the node.
        node->DelLink();
        delete node;

        // if the head is 0, then set the tail to 0 as well.
        if( m_head == 0 )
            m_tail = 0;
        
        m_count--;
    }

	// Gets an iterator pointing to the beginning of the list
    DoubleListIterator<DataType> GetIterator()
    {
        return DoubleListIterator<DataType>( this, m_head );
    }
};

template<class DataType>
class DoubleListIterator
{
public:
	DoubleListNode<DataType>*	m_node;		// pointer to the current node
	DoubleLinkedList<DataType>* m_list;		// pointer to the current list

public:
	DoubleListIterator( DoubleLinkedList<DataType>* p_list = 0,
						DoubleListNode<DataType>* p_node = 0 )
    {
        m_list = p_list;
        m_node = p_node;
    }
	// Determines if the node is valid
	bool Valid()
    {
        return (m_node != 0);
    }
	// Determines if two iterators point to the same node
	bool operator == ( DoubleListIterator<DataType>& p_rhs )
    {
        if( m_node == p_rhs.m_node && m_list == p_rhs.m_list )
        {
            return true;
        }
        return false;
    }
	// Resets the iterator to the beginning of the list
	void Start()
    {
        if( m_list != 0 )
            m_node = m_list->m_head;
    }
	// Resets the iterator to the end of the list
	void End()
    {
        if( m_list != 0 )
            m_node = m_list->m_tail;
    }
	// Moves the iterator forward by one position
	void Forth()
    {
        if( m_node != 0 )
            m_node = m_node->m_next;
    }
	// Moves the iterator backward by one position
	void Back()
    {
        if( m_node != 0 )
            m_node = m_node->m_previous;
    }
	// Gets the item that the iterator is pointing to
	DataType& Item()
    {
        return m_node->m_data;
    }
};

/**************************************************************************************
    HH    HH                    hh       TTTTTTTT          bb       ll              
    HH    HH                    hh          TT             bb       ll              
    HH    HH                    hh          TT             bb       ll              
    HH    HH   aaaaa    sssss   hhhhhh      TT     aaaaa   bbbbbb   ll   eeeee      
    HHHHHHHH  aa   aa  ss   ss  hhh  hh     TT    aa   aa  bbb  bb  ll  ee   ee     
    HH    HH       aa  ss       hh   hh     TT         aa  bb   bb  ll  ee   ee     
    HH    HH   aaaaaa   sssss   hh   hh     TT     aaaaaa  bb   bb  ll  eeeeeee     
    HH    HH  aa   aa       ss  hh   hh     TT    aa   aa  bb   bb  ll  ee          
    HH    HH  aa  aaa  ss   ss  hh   hh     TT    aa  aaa  bbb  bb  ll  ee   ee     
    HH    HH   aaaaaa   sssss   hh   hh     TT     aaaaaa  bbbbbb   ll   eeeee      
***************************************************************************************/
template< class KeyType, class DataType >
class HashEntry
{
public:
    KeyType m_key;
    DataType m_data;
};

template< class KeyType, class DataType >
class HashTable
{
public:
    typedef HashEntry<KeyType, DataType> Entry;

	int m_size;									// size of the table
	int m_count;								// the number of entries in the table
	OyArray< DoubleLinkedList<Entry>* > m_table;	// the actual table, a list of linked lists of entries.
	unsigned long int (*m_hash)(KeyType);		// a pointer to the hash function
public:

    HashTable( int p_size, unsigned long int (*p_hash)(KeyType) )
        : m_table( p_size )
    {
        m_size = p_size;
        m_hash = p_hash;
        m_count = 0;
		for( int i=0; i<m_table.Size(); i++ )
			m_table[i] = new DoubleLinkedList<Entry>();
    }
	~HashTable()
	{
		for( int i=0; i<m_table.Size(); i++ )
		{
			if(  m_table[i] )
				delete m_table[i];
			m_table[i] = NULL;
		}
	}

	// Gets the number of entries in the table
	int Count()
    {
        return m_count;
    }

	// Inserts a new key/data pair into the table
	void Insert( KeyType p_key, DataType p_data )
    {
        // create an entry structure.
        Entry entry;
        entry.m_data = p_data;
        entry.m_key = p_key;

        // get the hash value from the key, and modulo it so that it fits within the table.
        int index = m_hash( p_key ) % m_size;

        // add the entry to the correct index, increment the count.
        m_table[index]->Append( entry );
        m_count++;
    }

	// Finds a key in the table
	Entry* Find( KeyType p_key )
    {
        // find out which index the key should exist in
        int index = m_hash( p_key ) % m_size;

        // get an iterator for the list in that index.
        DoubleListIterator<Entry> itr = m_table[index]->GetIterator();

        // search each item
        while( itr.Valid() )
        {
            // if the keys match, then return a pointer to the entry
            if( itr.Item().m_key == p_key )
                return &(itr.Item());
            itr.Forth();
        }

        // no match was found, return 0.
        return 0;
    }

	// Removes an entry based on key
	bool Remove( KeyType p_key )
    {
        // find the index that the key should be in.
        int index = m_hash( p_key ) % m_size;

        // get an iterator for the list in that index.
        DoubleListIterator<Entry> itr = m_table[index]->GetIterator();

        // search each item
        while( itr.Valid() )
        {
            // if the keys match, then remove the node, and return true.
            if( itr.Item().m_key == p_key )
            {
                m_table[index]->Remove( itr );
                m_count--;
                return true;
            }
            itr.Forth();
        }

        // item wasn't found, return false.
        return false;
    }

};

/**************************************************************************************
       AA                                  SSSSSS                         kk        
       AA                                 SS    SS  tt                    kk        
      AAAA                                SS    SS  tt                    kk        
      AAAA   rrrrr rrrrr  aaaaa   yy  yy  SS       tttt  aaaaa    ccccc   kk  kk    
     AA  AA  rrr   rrr   aa   aa  yy  yy   SSSS     tt  aa   aa  cc   cc  kk kk     
     AA  AA  rr    rr         aa  yy  yy      SSS   tt       aa  cc       kkkk      
     AAAAAA  rr    rr     aaaaaa  yy  yy        SS  tt   aaaaaa  cc       kkk       
    AA    AA rr    rr    aa   aa   yyyy   SS    SS  tt  aa   aa  cc       kkkk      
    AA    AA rr    rr    aa  aaa   yyyy   SS    SS  tt  aa  aaa  cc   cc  kk kk     
    AA    AA rr    rr     aaaaaa    yy     SSSSSS    tt  aaaaaa   ccccc   kk  kk    
                                    yy                                              
                                  yyy                                               
***************************************************************************************/
//  Array stack implementation
template<class DataType>
class OyArrayStack : public OyArray<DataType>
{
public:
	int m_top;
public:
	OyArrayStack( int p_size ) : OyArray<DataType>( p_size )
    {
        m_top = 0;
    }
	bool Push( DataType p_data )
    {
        if( m_size != m_top )
        {
            m_array[m_top] = p_data;
            m_top++;
            return true;
        }
        return false;
    }
    void Pop()
    {
        if( m_top > 0 )
            m_top--;
    }
    DataType Top()
    {
        return m_array[m_top - 1];
    }
    int Count() const
    {
        return m_top;
    }
    void Resize( int p_size )
    {
        if( p_size < m_top )
        {
            m_top = p_size;
        }
        OyArray<DataType>::Resize( p_size );
    }
	void Clear()
	{
		m_top = 0;
	}

};


/**************************************************************************************
    BBBBBBB   ii                                  TTTTTTTT                            
    BB    BB  ii                                     TT                               
    BB    BB                                         TT                               
    BB    BB  ii  nnnnnn    aaaaa   rrrrr yy  yy     TT    rrrrr  eeeee    eeeee      
    BBBBBBB   ii  nn   nn  aa   aa  rrr   yy  yy     TT    rrr   ee   ee  ee   ee     
    BB    BB  ii  nn   nn       aa  rr    yy  yy     TT    rr    ee   ee  ee   ee     
    BB    BB  ii  nn   nn   aaaaaa  rr    yy  yy     TT    rr    eeeeeee  eeeeeee     
    BB    BB  ii  nn   nn  aa   aa  rr     yyyy      TT    rr    ee       ee          
    BB    BB  ii  nn   nn  aa  aaa  rr     yyyy      TT    rr    ee   ee  ee   ee     
    BBBBBBB   ii  nn   nn   aaaaaa  rr      yy       TT    rr     eeeee    eeeee      
                                            yy                                        
                                          yyy                                         
***************************************************************************************/
template<class DataType>
class BinaryTree
{
public:
	typedef BinaryTree<DataType> Node;

	DataType m_data;
	Node* m_parent;
	Node* m_left;
	Node* m_right;
public:
	BinaryTree()
    {
        m_parent = 0;
        m_left = 0;
        m_right = 0;
    }
	BinaryTree( DataType p_data )
    {
        m_parent = 0;
        m_left = 0;
        m_right = 0;
        m_data = p_data;
    }
	~BinaryTree()
    {
        Destroy();
    }

    void Destroy()
    {
        // if the left child exists, delete it.
        if( m_left )
            delete m_left;
        m_left = 0;

        // if the right child exists, delete it.
        if( m_right )
            delete m_right;
        m_right = 0;
    }

	// The number of nodes in the tree
	int Count()
    {
        // the count is set to 1, counting this node.
        int c = 1;

        // recursively add the counts of each child.
        if( m_left )
            c += m_left->Count();
        if( m_right )
            c += m_right->Count();

        // return the count.
        return c;
    }

	int GetDepth()
	{
		// start off with -1 for the depth of each child
		int left = -1;
		int right = -1;

		// calculate the depth of the left child
		if( m_left != 0 )
			left = m_left->GetDepth();

		// calculate the depth of the right child
		if( m_right != 0 )
			right = m_right->GetDepth();

		// take the larger of the two depths, add one, and return.
		return ( left > right ? left : right ) + 1;
	}
};

/**************************************************************************************
    BBBBBB   i                               SSSSS                                h       TTTTTTT                         
    B     B  i                              S     S                               h          T                            
    B     B                                 S     S                               h          T                            
    B     B  i  nnnnn    aaaa   r rr y   y  S         eeee    aaaa   r rr  cccc   h hhh      T    r rr  eeee    eeee      
    BBBBBB   i  n    n  a    a  rr   y   y   SSS     e    e  a    a  rr   c    c  hh   h     T    rr   e    e  e    e     
    B     B  i  n    n       a  r    y   y      SS   e    e       a  r    c       h    h     T    r    e    e  e    e     
    B     B  i  n    n   aaaaa  r    y   y        S  eeeeee   aaaaa  r    c       h    h     T    r    eeeeee  eeeeee     
    B     B  i  n    n  a    a  r     y y   S     S  e       a    a  r    c       h    h     T    r    e       e          
    B     B  i  n    n  a   aa  r     y y   S     S  e    e  a   aa  r    c    c  h    h     T    r    e    e  e    e     
    BBBBBB   i  n    n   aaa a  r      y     SSSSS    eeee    aaa a  r     cccc   h    h     T    r     eeee    eeee      
                                       y                                                                                  
                                     yy                                                                                   
***************************************************************************************/
template <class DataType>
class BinarySearchTree
{
public:
    typedef BinaryTree<DataType> Node;

	Node* m_root;
	int (*m_compare)(DataType, DataType);

public:
    BinarySearchTree( int (*p_compare)(DataType, DataType) )
    {
        m_root = 0;
        m_compare = p_compare;
    }
    ~BinarySearchTree()
    {
        // if the root exists, recursively delete the tree.
        if( m_root != 0 )
            delete m_root;
    }

    void Insert( DataType p_data )
    {
        Node* current = m_root;

        // if there is no root, then just put the new data
        // at the root.
        if( m_root == 0 )
            m_root = new Node( p_data );
        else
        {
            // else, you need to find where to insert the node.
            while( current != 0 )
            {
                // compare the data to insert with the current node
                if( m_compare( p_data, current->m_data ) < 0 )
                {
                    // test to see if the left child exists
                    if( current->m_left == 0 )
                    {
                        // if it doesnt exist, then insert the node
                        // as the left child.
                        current->m_left = new Node( p_data );
                        current->m_left->m_parent = current;
                        current = 0;
                    }
                    else
                    {
                        // else, go down to the left.
                        current = current->m_left;
                    }
                }
                else
                {
                    // test to see if the right child exists
                    if( current->m_right == 0 )
                    {
                        // if it doesn't exist, then insert the node
                        // as the right child.
                        current->m_right = new Node( p_data );
                        current->m_right->m_parent = current;
                        current = 0;
                    }
                    else
                    {
                        // else, go down to the right
                        current = current->m_right;
                    }
                }
            }
        }
    }

    Node* Find( DataType p_data )
    {
        Node* current = m_root;
        int temp;

        while( current != 0 )
        {
            // compare the data with the current nodes data.
            temp = m_compare( p_data, current->m_data );

            // if the data is equal, the node was found,
            // therefore, return it.
            if( temp == 0 )
                return current;

            // if the node was less than the current node, then
            // go to the left, else go to the right.
            if( temp < 0 )
                current = current->m_left;
            else
                current = current->m_right;
        }
        return 0;
    }

	inline int Count()
    {
        // recursively count the nodes starting at the root.
        if( m_root != 0 )
            return m_root->Count();
        return 0;
    }  
};

                                                                                          
/**************************************************************************************                                                                                          
     RRRRRRR    IIIIII  NNN  NNNNN   GGGGGG  FFFFFFFF   IIIIII   FFFFFFFF    OOOO         
      RR   RR     II     NN    NN   GG  GGG   FF   FF     II      FF   FF   OO  OO        
      RR   RR     II     NNN   NN  GG    GG   FF          II      FF       OO    OO       
      RR   RR     II     NNNN  NN  GG    GG   FF FF       II      FF FF    OO    OO       
      RR   RR     II     NNNN  NN  GG         FFFFF       II      FFFFF    OO    OO       
      RRRRRR      II     NN NN NN  GG  GGGGG  FF FF       II      FF FF    OO    OO       
      RR RR       II     NN  NNNN  GG    GG   FF          II      FF       OO    OO       
      RR  RR      II     NN  NNNN  GG    GG   FF          II      FF       OO    OO       
      RR   RR     II     NN   NNN   GG   GG   FF          II      FF        OO  OO        
     RRRR  RRR  IIIIII  NNNNN  NN    GGGGG   FFFFF      IIIIII   FFFFF       OOOO         
***************************************************************************************/
 /* 
 * Ring Buffer FIFO, no locking version 
 * Note that with only one concurrent reader and one concurrent writer, you don't need extra locking to use these functions. 
 */ 
template <class DataType>
class RingFIFO
{
public:
	unsigned int	_in;			// writer pos
	unsigned int	_out;			// reader pos
	unsigned int	_size;			// capacity 
	DataType		*_buffer;		// data

	// must call initialize after
	RingFIFO() : _in(0), _out(_in), _size(0), _buffer(NULL)
	{
	}
	RingFIFO( unsigned int capacity ) : _in(0), _out(_in), _size(capacity), _buffer(NULL)
	{
        _buffer = new DataType[_size];
	}

	virtual ~RingFIFO() 
	{
		if( _buffer )
		{
			delete [] _buffer;
			_buffer = NULL;
		}
	}

	void initialize(unsigned int capacity)
    {
        _in = 0;
        _out = _in;
        _size = capacity;
        if(_buffer)
        {
            delete[] _buffer;
            _buffer = NULL;
        }
        _buffer = new DataType[_size];
	}
	
	void clear()
    {
        _in = 0;
        _out = _in;
    }

	inline unsigned int getSize() const
    {
        if( _in >= _out )
        {
            return _in - _out;
        }
        else
        {
            return _size + _in - _out ;
        }
    }

	inline unsigned int getFreeSize() const
	{
		return _size - getSize();
	}

	// puts some data into the FIFO,
	unsigned int push( DataType *pBuffer, unsigned int len ) 
	{ 
		unsigned int l; 
		len = _MIN(len, _size - _in + _out); 
		/* first put the data starting from fifo->in to buffer end */ 
		l = _MIN(len, _size - (_in & (_size - 1))); 
		memcpy(_buffer + (_in & (_size - 1)), pBuffer, l*sizeof(DataType)); 
		/* then put the rest (if any) at the beginning of the buffer */ 
		memcpy(_buffer, pBuffer + l, (len - l)*sizeof(DataType)); 
		_in += len; 
		return len; 
	}

	// get some data into the FIFO,
	unsigned int pop( DataType *pBuffer, unsigned int len ) 
	{ 
		unsigned int l; 
		len = _MIN(len, _in - _out); 
		/* first get the data from fifo->out until the end of the buffer */ 
		l = _MIN(len, _size - (_out & (_size - 1))); 
		memcpy(pBuffer, _buffer + (_out & (_size - 1)), l*sizeof(DataType)); 
		/* then get the rest (if any) from the beginning of the buffer */ 
		memcpy(pBuffer + l, _buffer, (len - l)*sizeof(DataType)); 
		_out += len; 
		return len; 
	}
};                                                                                          

#endif